﻿// 1、双指针类型
// leetcode no.283 移动零
class Solution
{
public:
    void moveZeroes(vector<int>& nums)
    {
        int dest = -1;
        for (int cur = 0; cur < nums.size(); cur++)
        {
            if (nums[cur])
            {
                swap(nums[++dest], nums[cur]);
            }
        }
    }
};

// leetcode no.1089 复写零
class Solution 
{
public:
    void duplicateZeros(vector<int>&arr)
    {
        // 1. 先找到最后⼀个数 
        int cur = 0, dest = -1, n = arr.size();
        while (cur < n)
        {
            if (arr[cur]) dest++;
            else dest += 2;
            if (dest >= n - 1) break;
            cur++;
        }
        // 2. 处理⼀下边界情况 
        if (dest == n)
        {
            arr[n - 1] = 0;
            cur--; dest -= 2;
        }
        // 3. 从后向前完成复写操作 
        while (cur >= 0)
        {
            if (arr[cur]) arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};

// leetcode no.202 快乐数（快慢指针）
class Solution
{
public:
    int bitSum(int n) // 返回 n 这个数每⼀位上的平⽅和{ 
        int sum = 0;
    while (n)
    {
        int t = n % 10;
        sum += t * t;
        n /= 10;
    }
    return sum;
}
bool isHappy(int n)
{
    int slow = n, fast = bitSum(n);
    while (slow != fast)
    {
        slow = bitSum(slow);
        fast = bitSum(bitSum(fast));
    }
    return slow == 1;
}
};

//leetcode no.11 盛水最多的容器 
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int ret = 0;
        // 两层 for 枚举出所有可能出现的情况 
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 计算容积，找出最⼤的那⼀个 
                ret = max(ret, min(height[i], height[j]) * (j - i));
            }
        }


//2、滑动窗口（同向双指针）
// leetcode no.209 长度最小的子数组
class Solution
{
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int n = nums.size(), sum = 0, len = INT_MAX;
        for (int left = 0, right = 0; right < n; right++)
        {
            sum += nums[right]; // 进窗⼝ 
            while (sum >= target) // 判断 
            {
                len = min(len, right - left + 1); // 更新结果 
                sum -= nums[left++]; // 出窗⼝ 
            }
        }
        return len == INT_MAX ? 0 : len;
    }
};

//leetcode no.3 无重复字符的最长字串
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int hash[128] = { 0 }; // 使⽤数组来模拟哈希表 
        int left = 0, right = 0, n = s.size();
        int ret = 0;
        while (right < n)
        {
            hash[s[right]]++; // 进⼊窗⼝ 
            while (hash[s[right]] > 1) // 判断 
                hash[s[left++]]--; // 出窗⼝ 
            ret = max(ret, right - left + 1); // 更新结果 
            right++; // 让下⼀个元素进⼊窗⼝ 
        }
        return ret;
    }
};

//leetcode no.1004  最大连续1的个数 III
class Solution
{
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int ret = 0;
        for (int left = 0, right = 0, zero = 0; right < nums.size(); right++)
        {
            if (nums[right] == 0) zero++; // 进窗⼝ 
            while (zero > k) // 判断 
                if (nums[left++] == 0) zero--; // 出窗⼝ 
            ret = max(ret, right - left + 1); // 更新结果 
        }
        return ret;
    }
};
